public class Main {
    public static Long count = 1L;

    public static void main(String[] args) {
        // move(5, "X", "Y", "Z");
        char[] s = new char[]{'9', 'a', 'b', 'a', 'b', 'a', 'a', 'a', 'b', 'a'};
        char[] t = new char[]{'2','a', 'b', 'a'};
        char[] next = getNext(t);
        KMP(s, t, next);
        char[] next1 = getNext(s);

        /*System.out.println(next.length);*/

    }

    /**
     * 汉诺塔，移动次数是2^64 -1
     * 将64层从x 移动到z，
     * 1. 将上面63移动到y
     * 2.将 64 移动到z
     * 3. 将63从y借助x移动到z
     */
    public static void move(int n, String x, String y, String z) {

        if (n == 1) {
            // 只有一个的情况
            System.out.println(count + "次移动>>>>第" + n + "号盘子从" + x + "移动到" + z);
            count++;
        } else {
            // 将 x剩下的63个通过z移动到y上
            move(n - 1, x, z, y);
            System.out.println(count + "次移动>>>>第" + n + "号盘子从" + x + "移动到" + z);
            count++;
            // 将 y的63个通过x移动到z上
            move(n - 1, y, x, z);
        }
    }

    /**
     * next数组值当字符串失配时，我们应该用模式串的哪个字符串去比对
     *前缀是固定的，但是后缀是相对的，如果前缀与后缀相等，匹配的时候可直接匹配后缀，
     * 例：
     * 字符串S   aaaaaab
     *  模式串T aab,当第b在与a匹配的时候失配了，用T第二个a与S第四个a进行比较，不用从第一个a开始比较，
     * 通过一个前缀与后缀进行计算得来
     * @param chars
     * @return
     */
    public static char[] getNext(char[] chars) {
        char[] next = new char[chars.length];
        next[1] = 0;
        int i = 1, j = 0;

        while (i < Integer.parseInt(String.valueOf(chars[0]))) {
            // 前缀与后缀相等，next数组值为前缀的索引
            if (j == 0 || chars[i] == chars[j]) {
                i++;
                j++;
                next[i] = (char) j;
            } else {
                // 前缀与后缀相等，next数组值回溯到上一次j的next数组值
                j = next[j];
            }
        }
        return next;
    }

    /**
     * 规定数组第一个个元素存数组字符串的长度
     *
     * @param s    目标串
     * @param t    模式串
     * @param next next数组---当字符串失配时，应该从模式串哪个位置进行匹配
     */
    public static void KMP(char[] s, char[] t, char[] next) {
        int sIndex = 1; // 目标串s的索引
        int tIndex = 1; // 模式串t的索引
        int tLength = Integer.parseInt(String.valueOf(t[0]));

        while (sIndex <= Integer.parseInt(String.valueOf(s[0]))) {
            /**
             * 字符匹配成功
             */
            if (s[sIndex] == t[tIndex]) {
                /***
                 * 模式串长度到达最后
                 */
                if (tIndex == tLength) {
                    System.out.println("匹配成功,s串索引值" + (sIndex - tLength + 1));
                    /**
                     * 下面这2步是我大胆假设的结果，不确定对不对，经过测试，好像没有问题
                     * 如果已经匹配了，s串后一位与T串最后一位的next数组的下一位比对
                     */
                    sIndex++;
                    tIndex = next[tIndex] + 1;
                } else {
                    /**
                     * 未到最后，进行下一位比对
                     */
                    sIndex++;
                    tIndex++;
                }
            } else {
                /**
                 * 前面第一位都不匹配，直接匹配s串下一位
                 */
                if (tIndex <= 1) {
                    sIndex++;
                } else {
                    /**
                     * 通过next数组决定下一位匹配哪个位置
                     */
                    tIndex = next[tIndex];
                }
            }
        }

    }
}
